
//1920.基于排列构建数组
class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        //使用O(1)的时间复杂度实现
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            int x=nums[i];
            if(x<0) continue;   //如果小于0说明该位置已经被修改了，继续下一个位置

            int hole=i;  // 当前位置需要被填
            int j=nums[i];   //hole的下一个位置下标
            while(j!=i)
            {
                nums[hole]=-(nums[j]+1);   //将坑填起来
                
                hole=j;     //继续下一个位置
                j=nums[hole];
            }
            nums[hole]=-(x+1);  //将回到i位置的前一个位置进行修改
        }

        for(int i=0;i<n;i++)
        nums[i]=-nums[i]-1;   //将数组还原

        return nums;
    }
};